use petgraph::graph::{DiGraph, NodeIndex};
use petgraph::algo::dijkstra;
use petgraph::dot::{Dot};
use std::ops::Add;

// 自定义的边类型
#[derive(Debug, Clone, PartialEq, PartialOrd, Default)]
struct EdgeType {
    weight: f64,  // 边的权重
    info: String, // 可选的额外信息
}

impl Add<EdgeType> for EdgeType {
    type Output = EdgeType;
    fn add(self, rhs: EdgeType) -> Self::Output {
        EdgeType {
            weight: self.weight + rhs.weight,
            info: format!("{}+{}", self.info, rhs.info),
        }
    }
}

// impl<'a> Add<&'a EdgeType> for &'a EdgeType {
//     type Output = &'a EdgeType;
//     fn add(mut self, rhs: &'a EdgeType) -> Self::Output {
        
//     }
// }

// impl petgraph::algo::Measure for EdgeType {
// }


fn main() {
    // 创建一个有向图，NodeIndex代表图中的节点
    let mut graph = DiGraph::<&str, EdgeType>::new();

    // 添加节点
    let a = graph.add_node("A");
    let b = graph.add_node("B");
    let c = graph.add_node("C");
    let d = graph.add_node("D");

    // 添加带有自定义边权重的边
    graph.add_edge(a, b, EdgeType { weight: 3.0, info: String::from("AB") });
    graph.add_edge(b, c, EdgeType { weight: 2.0, info: String::from("BC") });
    graph.add_edge(a, c, EdgeType { weight: 5.0, info: String::from("AC") });
    graph.add_edge(c, d, EdgeType { weight: 1.0, info: String::from("CD") });

    // 查找从节点a到d的最短路径
    let start = a;
    let end = d;

    // 使用Dijkstra算法找到最短路径
    let result = dijkstra(&graph, start, Some(end), |e| e.weight().weight);
    print!("{:?}", result)

    // println!("最短路径长度: {}", result.0);
    // println!("路径: {:?}", result.1);
}
